package 纯01问题携带研究材料;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/6 16:29
 * @description:
 */
public class Solution {
    public int zoneOne(int goods, int luggage, int[] weights, int[] values) {
        // 01背包问题
        // ① dp数组以及含义：dp[i][j]表示从 0-i 中选取物品，当背包容量为 j 时，所能携带的最大价值
        // ② 动态转移方程：dp[i][j] = Math.max(dp[i-1][j], dp[i-1][ j-weights[i] ] + values[i])。每一个物品都拥有选取/不选取两种状态
        // ③ 初始化dp数组：dp[i][0] = 0 当背包容量为0时，是存放不了价值的。dp[0][j] 当只含有物品0时，背包容量需要大于value才能存放
        // ④ 遍历顺序：可以先遍历物品，再遍历背包容量。反之其实也可以

        int[][] dp = new int[goods][luggage + 1];
        for (int i = weights[0]; i <= luggage; i++) {
            dp[0][i] = values[0];
        }
        print(dp);
        for (int i = 1; i < goods; i++) {
            for (int j = 0; j <= luggage; j++) {
                if (j < weights[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
                }
            }
            print(dp);
        }

        return dp[goods - 1][luggage];
    }


    public void print(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println("--------------------------");
    }
}
